package com.leetcode.code;

import java.util.Arrays;

/**
 * Description:
 *
 * @author zkingcobra
 * Date: 2020/1/15 3:44 下午
 */
public class LeetCode0056Java {
    public static void main(String[] args) {

        SolutionFastest solution = new SolutionFastest();
        int[][] sss = solution.merge(new int[][] {
                //new int[] { 2, 6 }, new int[] { 1, 3 }, new int[] { 3, 12 }, new int[] { 8, 10 }, new int[] { 15, 18 },
                //new int[] { 15, 18 }, new int[] { 8, 10 }, new int[] { 115, 118 }
                new int[] { 1, 3 }, new int[] { 4, 6 }, new int[] { 3, 4 }, new int[] { 8, 10 }, new int[] { 15, 18 }
        });

        System.out.println(Arrays.deepToString(sss));
    }

    /**
     * 最快的版本
     * 连通块
     */
    static class SolutionFastest {
        public int[][] merge(int[][] intervals) {
            int len = intervals.length;

            for (int i = 0; i < intervals.length; i++) {
                int width_i = intervals[i][1] - intervals[i][0];

                for (int j = i + 1; j < intervals.length; j++) {
                    int width_j = intervals[j][1] - intervals[j][0];

                    int right = Math.max(intervals[i][1], intervals[j][1]);
                    int left = Math.min(intervals[i][0], intervals[j][0]);

                    if ((width_i + width_j) >= (right - left)) {
                        intervals[j][0] = left;
                        intervals[j][1] = right;
                        intervals[i] = null;
                        len--;
                        break;
                    }
                }
            }
            // 没有合并
            if (len == intervals.length) {
                return intervals;
            }

            // 有合并
            int[][] ints = new int[len][];
            int i = 0;
            for (int[] interval : intervals) {
                if (interval != null) {
                    ints[i++] = interval;
                }
            }

            return ints;
        }
    }
}
